package com.cqs.leetcode.backtrack;

import java.util.function.IntFunction;

/**
 * @author lixiaowen
 * @create 2019-12-18
 */
public class PermutationSequence60 {

    private String result = null;
    private int count = 0;

    public String getPermutation(int n, int k) {
        this.count = k;
        permutation(n, 0, new boolean[n], "");
        return result;
    }

    private void permutation(int n, int level, boolean[] used, String prefix) {
        if (level == n) {
            --count;
            if (count == 0) {
                result = prefix;
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            permutation(n, level + 1, used, prefix + (i + 1));
            used[i] = false;
        }
    }


    private static class Solution{

private String result = null;

public String getPermutation(int n, int k) {
    permutation(n,k,new boolean[n],"");
    return result;
}

/**
 * 关键理解
 * 1. 递归
 * 2. order,groupSize,group的变化
 *
 * @param n
 * @param order
 * @param used 状态记录:哪些数字使用了
 * @param subResult
 */
private void permutation(final int n, final int order, boolean[]  used, final String subResult ){
    //处理第几层了
    int level = subResult.length();
    if (level == n ){
        this.result = subResult;
        return;
    }
    IntFunction<Integer> factories = value -> {
        if (value == 0 ) return 1;
        int result = 1;
        for (int i = 2; i <=value ; i++) {
            result *= i;
        }
        return result;
    };
    //每次对剩下的(n-1-level)!分组
    int groupSize = factories.apply(n - 1 - level);
    //进行分组: [0 ... (n -1 - level)];
    int groups = (order - 1) / groupSize ;
    int cnt = -1;
    int i = 0;
    //数字从小到大的方向遍历
    for (i = 0; i < used.length; i++) {
        if (used[i]) continue;
        if (++cnt == groups){
            //记录已经使用的数字[下标]
            used[i] = true;
            break;
        }
    }
    permutation(n, order - groups * groupSize, used, subResult + (i+1));
}

    }


    public static void main(String[] args) {
        int n = 5;
        int times = 1;
        for (int i = 2; i <= n; i++) {
            times *= i;
        }
        PermutationSequence60 permutation = new PermutationSequence60();
        Solution solution = new Solution();
        for (int i = 0; i < times; i++) {
            int k = i + 1;
            String result = solution.getPermutation(n, k);

            System.out.println(k + "\t" + result + "\t" + permutation.getPermutation(n,k));
        }
    }
}

